Introduction aux algorithmes de tri

Qu’est-ce qu’un tri ?

Un tri est un procédé algorithmique qui consiste à réorganiser les éléments d’un tableau ou d’une collection selon un certain ordre, le plus souvent croissant ou décroissant.

Par exemple :
Avant tri : [42, 7, 19, 3]
Après tri croissant : [3, 7, 19, 42]

Pourquoi trier des données ?

Les algorithmes de tri sont fondamentaux en informatique. Voici pourquoi :

1. Améliorer la recherche

• Une fois triées, les données peuvent être recherchées plus rapidement.
• Exemple : la recherche dichotomique (binaire) ne fonctionne que sur un tableau trié.
  • Temps de recherche non trié : O(n)
  • Temps de recherche trié avec dichotomie : O(log n)

2. Faciliter l’analyse

• Trier des données permet de :
  • repérer plus facilement des valeurs extrêmes (minimum/maximum),
  • calculer des médianes,
  • détecter des doublons,
  • ou encore identifier des tendances.

3. Préparer des affichages

• Les interfaces utilisateurs attendent souvent des données ordonnées :
  • Trier par nom, date, prix, score, etc.

4. Optimiser d’autres algorithmes

• De nombreux algorithmes deviennent plus simples ou plus rapides si les données sont triées :
  • Compression
  • Fusion de fichiers
  • Comparaison d’ensembles
  • Traitement de flux de données

Exemple concret : Recherche plus rapide

Imaginons un tableau de 10 000 noms non triés. Pour chercher “Martin” :

• Si le tableau n’est pas trié : on doit regarder un à un → jusqu’à 10 000 comparaisons.
• Si le tableau est trié : on utilise la recherche binaire → au pire 14 comparaisons (car log₂(10000) ≈ 14).

Conclusion

Même si trier consomme du temps, cela permet de sauver énormément de temps plus tard.
C’est un investissement algorithmique : on paie une fois pour ensuite accélérer toutes les opérations qui suivent.

C’est pourquoi les tris sont parmi les premiers algorithmes enseignés en informatique :
ils sont simples à comprendre, très utiles, et ouvrent la porte à des concepts plus avancés comme la complexité, les structures de données, et les algorithmes de recherche.

Qu’est-ce que la fouille séquentielle ?

Définition

La fouille séquentielle (ou recherche linéaire) est la méthode la plus simple pour retrouver une valeur dans un tableau ou une liste.

• Elle consiste à parcourir les éléments un par un, du début jusqu’à la fin, jusqu’à ce qu’on trouve la valeur cherchée (ou qu’on atteigne la fin du tableau sans la trouver).
• N'exige pas que les éléments du tableau soient ordonnés.
• S'il y a plusieurs occurrences de la même valeur dans le tableau retourne la position de la première occurrence.
• Dans le pire des cas (si la valeur recherchée n'est pas dans le tableau) le nombre d'éléments consultés sera égal au nombre d'éléments dans le tableau.
• Principe: tant que la valeur recherchée n'est pas trouvée et que le tableau n'est pas à la fin -> avancer au prochain élément.

Exemple simple

public static int fouilleSequentielle(int[] tableau, int valeur) {
    for (int i = 0; i < tableau.length; i++) {
        if (tableau[i] == valeur) {
            return i; // On a trouvé !
        }
    }
    return -1; // Pas trouvé
}

Caractéristiques

Caractéristique	Détail
Fonctionne sur	Tout type de données, triées ou non
Complexité temps	O(n) dans le pire des cas
Complexité mémoire	O(1) (pas de mémoire additionnelle)
Avantage	Très simple à implémenter
Inconvénient	Lent si le tableau est grand

Exemple :

Si on cherche 5 dans le tableau [3, 8, 1, 5, 9] :

• Compare avec 3 → non
• Compare avec 8 → non
• Compare avec 1 → non
• Compare avec 5 → trouvé ! (à l’index 3)

En résumé

• La fouille séquentielle est la méthode de base pour chercher une valeur.
• Elle est fiable et universelle, mais inefficace pour de grands tableaux.

---

Le pire tri possible : Bogo Sort

Pour apprécier à quel point un bon algorithme de tri compte, rien de mieux qu'un contre-exemple absurde.

Bogo Sort (aussi appelé stupid sort ou monkey sort) fonctionne ainsi :

1. Est-ce que le tableau est trié ? Si oui → terminé.
2. Sinon → mélanger aléatoirement tous les éléments et recommencer.

import java.util.Random;

public static void bogoSort(int[] arr) {
    while (!estTrie(arr)) {
        melanger(arr);
    }
}

private static boolean estTrie(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

private static void melanger(int[] arr) {
    Random rand = new Random();
    for (int i = arr.length - 1; i > 0; i--) {
        int j = rand.nextInt(i + 1);
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
}

Complexité : O(n!)

Il y a n! façons d'ordonner n éléments. En moyenne, il faudra essayer n! / 2 permutations avant de tomber sur la bonne par hasard.

n	n!	Tentatives moyennes
3	6	~3
5	120	~60
10	3 628 800	~1 800 000
20	2 432 902 008 176 640 000	des années...

Bogo Sort sur 20 éléments prendrait en moyenne des milliers d'années sur un ordinateur moderne.

Pourquoi en parler ?

Pas pour l'utiliser — mais pour comprendre viscéralement pourquoi la complexité algorithmique existe. Tous les algorithmes de tri vus dans ce cours (Insertion Sort, Heap Sort) ont été conçus pour éviter exactement ça.